package ACWing.SearchAndGraphTheory.DFS;
//843. n-皇后问题
import java.util.Scanner;

/**
 * @author :chenjie
 * @date :Created 2022/12/15 22:13
 */
public class NQueensRroblem {
    static String[][]arr=new String[20][20];//用截距来判断b=y+x所以有可能是20所以用20
    //分别对应行类和俩个对角线的情况
    static boolean[]col=new boolean[20];
    static boolean[]dg=new boolean[20];
    static boolean[]udg=new boolean[20];
    static boolean[]row=new boolean[20];
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j]=".";
            }
        }
        //dfs(0,n);
        dfs2(0,0,0,n);
    }
    public static void dfs(int u,int n){
        if(u==n){
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    System.out.print(arr[i][j]);
                }
                System.out.println();
            }
            System.out.println();
            return;
        }
        for (int i = 0; i < n; i++) {
            if(!col[i]&&!dg[u+i]&&!udg[n-u+i]){//精华所在用截距来判断对角线
                arr[u][i]="Q";
                col[i]=dg[u+i]=udg[n-u+i]=true;
                dfs(u+1,n);
                col[i]=dg[u+i]=udg[n-u+i]=false;
                arr[u][i]=".";
            }
        }
    }
    //解法二与上解法的差别在于解法二通过递归遍历了整个节点去判断是否要放皇后解法一是通过循环去判断一整行如何递归到下一行
    public static void dfs2(int x,int y,int s,int n){
        //设置边界条件
        if(y==n){
            y=0;
            x++;
        }
        if(x==n){
            if(s==n){
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n; j++) {
                        System.out.print(arr[i][j]);
                    }
                    System.out.println();
                }
                System.out.println();
            }return;
        }

        //不放皇后
        dfs2(x,y+1,s,n);

        //放皇后
        if(!row[x]&&!col[y]&&!dg[x+y]&&!udg[x-y+n]){//条件允许的情况下放皇后
            arr[x][y]="Q";
            row[x]=col[y]=dg[x+y]=udg[x-y+n]=true;
            dfs2(x,y+1,s+1,n);
            row[x]=col[y]=dg[x+y]=udg[x-y+n]=false;
            arr[x][y]=".";
        }
    }
}
